package com.algrithom.tree.bst;

import com.common.model.TreeNode;
import com.util.TreeOperUtil;

/**
 * 235. 二叉搜索树的最近公共祖先
 *
 * @author think
 */
public class Solution1 {
    
    public static void main(String[] args){
        Integer[] array = new Integer[]{6,2,8,0,4,7,9,null,null,3,5};
        TreeNode<Integer> root = TreeOperUtil.createTree(array,0);
        Solution1 solution1 = new Solution1();
        TreeNode<Integer> result = solution1.lowestCommonAncestor(root,2,2);
        System.out.println(result.getValue());
    }
    
    private TreeNode<Integer> lowestCommonAncestor(TreeNode<Integer> root,int p,int q){
        // 如果根节点和p,q的差相乘是正数，说明这两个差值要么都是正数要么都是负数，也就是说
        // 他们肯定都位于根节点的同一侧，就继续往下找
        //        if ((root.getValue() - p) * (root.getValue() - q) <= 0) {
        //            return root;
        //        }
        //        return p < root.getValue() ? lowestCommonAncestor(root.getLeftChild(), p, q)
        //                : lowestCommonAncestor(root.getRightChild(), p, q);
        while ((root.getValue() - p) * (root.getValue() - q) > 0) {
            root = p < root.getValue() ? root.getLeftChild() : root.getRightChild();
        }
        // 如果相乘的结果是负数，说明p和q位于根节点的两侧，如果等于0，说明至少有一个就是根节点
        return root;
    }
}